package LimitedTimeGame.Day_0222;

/**
 * @author zxc
 * @date 2023/02/22 08:19
 **/

/**
 * 题目 ：石子游戏二
 * 题目详述 ：
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
 * 0 <= j <= nums[i]
 * i + j < n
 * 返回到达nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 *
 * 提示:
 * 1 <= nums.length <= 104
 * 0 <= nums[i] <= 1000
 * 题目保证可以到达 nums[n-1]
 *
 */
public class Jump {
    public static void main(String[] args) {
        System.out.println(jump(new int[]{3,4,3,2,5,4,3}));
    }
    /**
     * 思路 ：
     * 即，计算每次跳跃所能够到达的最远距离
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        int len = nums.length;
        // 特殊情况 ：nums数组中有且仅有一个元素，不需要跳跃
        if(len == 1){
            return 0;
        }
        int k = 1;
        int count = 0;
        // 当前跳跃所能够到达的最远距离
        int last = k + nums[0] - 1;
        // 变量k，所指向的是下一次开始遍历的首个元素;
        while(k < len){
            // 记录当前本次跳跃所需要遍历的数目（从k开始进行遍历[包括k，因为 k所指向的是下一次遍历的首个元素];）
            int distance = last - k + 1;
            // 退出循环时 ：k = k + step;
            while(k < len && distance > 0){
                // 记录当前跳跃所能够到达的最远距离
                last = Math.max(last , k + nums[k]);
                k++;
                distance--;
            }
            count++;
        }
        return count;
    }
}
